Quantum Factoring Performance Evaluation - Using Parallel Programming - VB2022

Picture 1a VB2019 Test 8 CF VB2019 Test 8 MF - Selected

Picture 1b VB2022 Test 8 CF VB2022 Test 8 MF - Selected

Picture 2a VB2022 Test -6

Picture 2a VB2022 Test -6

1. Picture 1A shows "Control Form" of program: "VB2019 Findprim QC" in order to do prime number factorization of Test 8.
   When the Picture is selected the "Monitor Form" is displayed.
2. Picture 1B shows "Control Form" of program: "VB2022 Findprim QC" in order to do prime number factorization of Test 8.
   When the Picture is selected the "Monitor Form" is displayed.
   The duration is smaller.
3. Picture 2A shows "Control Form" of program: "VB2022 Findprim QC" to test the T2,T3 etc functionality.
   When the Picture is selected the "Monitor Form" is displayed. This is important to demonstrate that this functionality also works with parallel processing.
   For a detailed explanation of this functionality select: findprim_array_x.xls.htm Excel is used because excesive data has to be displayed.

Performance evalution

The following table shows the perfomance evalution to factorize large numbers of different sizes using one, two three or four processors.

In order to understand the program "VB2019 FindPrim QC" the user should study : Answer question 11 - Calculating Periodicity in 5 easy steps Specific study Example 4 and the concepts amax and amin. The difference between those two parameters is the period.
The Visual Basic "VB2019 FindPrim QC" program follows the same 5 steps.

1. In test 2 the number to factorize n = 12301866871170953183 which consists of two prime numbers: pm1 = 3347807173 and pm2 = 3674604371. See Picture 2 below
   Calculate (n+1)/2. This is 6150933435585476592
   Calculate sqr(n). This is the number 3507401726
   Subtract those two numbers. You get : 6150933432078074866. This is amax. This number is larger than the periodicity.
2. Now calulate 2 ^ amax mod n or 2 ^ 6150933432078074866 mod 12301866871170953183. You get : 1787540236663610903. This is the stop sign.
3. Now calculate 2 ^ amin mod 12301866871170953183 = 1787540236663610903 (stop sign)
   This is a "difficult" calculation. See below for more detail. The value you should get is amin = 3804046
4. Now subtract amin from amax. The value you get is 615093343274270820. That is the period.
   Divide period by 2 or 615093343274270820 by 2. You get: 3075466716037135410. This is per2
   Now perform 2 ^ per2 mod n or 2 ^ 3075466716037135410 mod 12301866871170953183. You get 3151404462955436851. This is y.
5. Now perform GCD (y+1,n) and GCD(y-1,n). The results are the two prime numbers searched for.

• To read more detail about VB2019 select this link: VB2019 shor-findprim_QC.htm Quantum Factoring Performance Evaluation - Using Parallel Programming - VB2019
  
• To read more about Microsoft problems in 2023 select this link: Carpe Diem versus Evaluation and Criticism Microsoft in 2023

"VB2022 FindPrim QC" Program source.

VB2022 FindPrim QC Details

Picture 3a VB2019 Test 7

Picture 3b VB2022 Test 0

Picture 3c VB2022 Test 7

To investigate the reason consider Picture 3b. This shows the factorization of n = 10823, which the product of the two prime numbers 79 and 137.
Five calculations are important:

1. The first involves the period calculation which uses amax, amin
   amax is calculated as: amax = (n+1)/2 + sqr(n) = 5308
   amin is the same as acalc. acalc is calculated as: acalc = amin = (pm1+pm2)/2 - sqr(n) = 108 - 104 = 4
   The period calculation is: period = amax - amin. In this example period = 5308 - 4 = 5304
2. All the following calculations involve Modular 2 Exponention in the form of: 2^a mod n = xn The second calculation is the amax stop sign calculation: 2^amax mod n = 2^5308 mod n = 16.
3. The third calculation is the amin stop sign calculation: 2^amin mod n = 2^4 mod n = 16.
4. the fourth calculation is: 2^ period mod n = 2^ 5304 mod n = 1
5. The fifth equation is: 2^amax mod n = (2 ^ amin mod n) * (2^ period mod n) or 2^5308 mod n = (2 ^ 4 mod n) * (2^ 5304 mod n) or 16 = 16 * 1
   

In that case the print output (with the Debug.Print statement) of the subroutine Main_Int shows:

1. Test 0 with n=10823
   Main_Int 1 Modular_2_exp_Int_array 2^amax mod n = 2^5308 mod 10823 = 16
   Main_Int 2 Modular_2_exp_Int_array 2^amin mod n = 2^4 mod 10823 = 16
   Main_Int 4 Modular_2_exp_Int_array 2^period mod n = 2^5304 mod 10823 = 1 Should be 1
   In Test 0 with n=10823 the two stop signs when a=amax and when a=amin are the same.
2. With Test 7 the printer output shows:
   trace 11 pm1 334780716989911 pm2 367460436668101
   Main_Int 1 Modular_2_exp_Int_array 2^amax mod n = 2^61509334226585966991263981415 mod 123018668453172635462872529011 = 52424584213408915799818872402
   Main_Int 2 Modular_2_exp_Int_array 2^amin mod n = 2^380404545915 mod 123018668453172635462872529011 = 80742077899938844980887887032
   Main_Int 4 Modular_2_exp_Int_array 2^61509334226585966610859435500 mod 123018668453172635462872529011 = 59345945384029708177592406792 Should be 1
   In Test 7 the two stop signs when a=amax and when a=amin are different.
3. Test 8
   trace 11 pm1 334780716989903 pm2 367460436668111
   Main_Int 1 Modular_2_exp_Int_array 2^amax mod n = 2^61509334226586171053102258526 mod 123018668453173043586549083233 = 45974955432214577569296125968
   Main_Int 2 Modular_2_exp_Int_array 2^amin mod n = 2^380404545916 mod 123018668453173043586549083233 = 45974955432214577569296125968
   Main_Int 4 Modular_2_exp_Int_array 2^61509334226586170672697712610 mod 123018668453173043586549083233 = 1 Should be 1
   In Test 8 the two stop signs when a=amax and when a=amin are the same.
   Maint_Int is the subroutine executed after the "Start push button" is selected, part of the program "VB2019 FindPrim QC".

Historical overview

Before the the loop is executed the following two statement are performed: a = 1 and xn = 2
Within this loop 3 calculations are performed:1) a = a + 1 and 2)xn = xn * 2 and 3) if xn>n then xn = xn -n
The loop is terminated when xn = stop sign. At that moment amin = a.

The question can be raised if there is nothing to warn in advance, that something is wrong. The answer is yes. Like you can calculate the stop sign at amax using modular 2 exponentation, you can also calculate the stop sign at acalc, which is the predicted value of amin. Both these stop signs should be equal.
The predicted period, which is the difference between amax and acalc (amin), can also be tested.
Both these can be used in advance if amin can be calculated and factorization will work.

The conclusion is that the origin of that Test 7 uses two prime numbers which are no prime numbers.
The problem arises because Test 7 uses two predefined numbers which were supposed to be prime numbers, but are not. To solve that the parameter Control_Form.TTprime.Text should have been set to 1. "T Tprime" means "Test prime numbers".
What this means that there is nothing wrong with the factorization algorithm used.

However still there is a problem. The problem is that Picture 3a shows a solution, which seems to be correct, but it is not. Something is wrong with the software.

To investigate what is wrong two test are performed:

1. One test identical as Test 0, with pm1 = 33478079 and with pm2 36746063. This test is used to demonstrate factorization of two prime numbers.
   The results are shown in Table 3A and Table 4A.
2. And a second test with pm1 = 33478079+2 and with pm2 = 36746063+2. This test is used demonstrate factorization of two odd numbers, identical as Test 7.
   The results are shown in Table 3B and Table 4B. (Both should indicate an error)

And this with two programs:

1. One with the original program "VB2019 FindPrim QC" as used in Test 7 picture 3A. The results are in Table 3A and 3B.
2. One with a corrected version of "VB2019 FindPrim QC". This is the same as "VB2022 Findprim QC".The results are in Table 4A and 4B.

pm1 33478079 pm2 36746063 n 1230187600052977
Main (pm1+pm2)/2 35112071   sqr(n) 35074030   amin 38041   amax 615093764952459
period  615093764914418 Stop sign 1
Stop sign amax 562856816646609 Lc 50  9  764952459
Stop sign amin 562856816646609 Lc 16  9  38041
Geta_mod2_PP Start  0 xval   562856816646609
Geta_mod2_PP Start  0 n   1230187600052977
Geta_mod2_PP  np 1
Geta_mod2_PP 5 a  38041 lxn 2 ln 2 n 1230187600052977 xn 1793044416699586
Geta_mod2_PP 6 a  38041 lxn 2 ln  2 test  1 xn 562856816646609
Geta_mod2_PP 7 a  38041  0  1 cnt 42 xn 562856816646609 str_xval 562856816646609
Geta_mod2_PP 8 FinishedSt   pr_end 1 test 0 np 1
Geta_mod2_PP 9 FinishedSt pp1  38041 pp2  0 pp3  0 pp4  0
Geta_mod2_PP 10 FinishedSt  aa(2)  0  38041 pr_end 1 np 1
    type? y  p 36746063 q 33478079 Dtime 0.12512460000289138 125 msec

pm1 33478081 pm2 36746065 n 1230187740501265
Main (pm1+pm2)/2 35112073   sqr(n) 35074032   amin 38041   amax 615093835176601
period  615093835138560 Stop sign 822998510771711
Stop sign amax 1029155177293882 Lc 50  9  835176601
Stop sign amin 523600715693967 Lc 16  9  38041
Geta_mod2_PP Start  0 xval   523600715693967
Geta_mod2_PP Start  0 n   1230187740501265
Geta_mod2_PP  np 1
Geta_mod2_PP 5 a  38041 lxn 2 ln 2 n 1230187740501265 xn 1753788456195232
Geta_mod2_PP 6 a  38041 lxn 2 ln  2 test  1 xn 562856816646609
Geta_mod2_PP 7 a  38041  0  1 cnt 42 xn 523600715693967 str_xval 523600715693967
Geta_mod2_PP 8 FinishedSt   pr_end 1 test 0 np 1
Geta_mod2_PP 9 FinishedSt pp1  38041 pp2  0 pp3  0 pp4  0
Geta_mod2_PP 10 FinishedSt  aa(2)  0  38041pr_end 1 np 1
    type ?  y  p 36746065 q 33478081 Dtime 0.11905409999599215 119 msec

pm1 33478079 pm2 36746063 n 1230187600052977
Main (pm1+pm2)/2 35112071   sqr(n) 35074030   acalc 38041   amax 615093764952459
period  615093764914418 Mod 2 Expo 1 SHOULD BE 1
trace 11 pm1 33478079 pm2 36746063
Main_Int 1 Modular_2_exp_Int_array 2^615093764952459 mod 1230187600052977 = 562856816646609 = a
Main_Int 2 Modular_2_exp_Int_array 2^38041 mod 1230187600052977 = 562856816646609 = a
Main_Int 4 Modular_2_exp_Int_array 2^615093764914418 mod 1230187600052977 = 1 Should be 1 
Main_Int Step 5 stop sign : 562856816646609 xn5(1)  1 str_xn5$ 1
Geta_mod2_PP Start  0 xval   562856816646609
Geta_mod2_PP Start  0 n   1230187600052977
Geta_mod2_PP  np 1
Geta_mod2_PP 6  a 38041 lxn 2 ln 2 test 1 xn562856816646609
Geta_mod2_PP 7  a 38041  0  1 cnt 42 xn 562856816646609 str_xval 562856816646609
Geta_mod2_PP 8 FinishedSt   prn_end 1 test 0 np 1
Geta_mod2_PP 9 FinishedSt pp1  38041 pp2  0 pp3  0 pp4  0 prn_end  1
Geta_mod2_PP 10 FinishedSt  aa(2)  0 aa(1)  38041pr_end  1 np 1
    type ? y  p 36746063 q 33478079 Dtime 0.19318809999822406 193 msec

pm1 33478081 pm2 36746065 n 1230187740501265
Main_Int Step 3a acalc : 38041 amin predicted = (pm1+pm2)/2 - sqr(n) 
Main (pm1+pm2)/2 35112073   sqr(n) 35074032   acalc 38041   amax 615093835176601
Main_Int Step 4 amax : 615093835176601
period  615093835138560 Mod 2 Expo 822998510771711 SHOULD BE 1
Main_Int 1 Modular_2_exp_Int_array 2^615093835176601 mod 1230187740501265 
                                                                = 1029155177293882 = a
Main_Int 2 Modular_2_exp_Int_array 2^38041 mod 1230187740501265 = 523600715693967 = a
Main_Int 4 Modular_2_exp_Int_array 2^615093835138560 mod 1230187740501265 
                                                         = 822998510771711 Should be 1 
Geta_mod2_PP Start  0 xval   1029155177293882
Geta_mod2_PP Start  0 n   123018740501265
Geta_mod2_PP  np 1
Geta_mod2_PP 6  a  38041 lxn 2 ln 2 test 1 xn 523600715693967
Geta_mod2_PP 7  a 38041 -1  1 cnt 42 xn 523600715693967 str_xval 1029155177293882
Geta_mod2_pp 40000

Table 3A

Table 3B

Table 4A

Table 4B

The present situation - as of 5 August 2023

How ever a much more serious problem is to detect errors in the complicated software as demonstrated above. The main reason is that special integer array subroutines are used.
The advantage of a PC is when the same program is executed again the same errors will pop up.

In the Quantum Computer, most probably is prone to the following errors:

1. Errors in the Hardware related to the stability issues of Qubits.
2. Errors in the logic primarily to calculate the Period.

IMO, in a QC there is an additional problem: When the same program is executed again, there is no quarantee that the same error will pop up.

First I would like to make a comment. At of this moment it is not clear to me how any application on a QC is implemented.

1. On a PC this is done by writing a software program.
2. On an analog computer this is done by building your application by means of a patch board. (As far as I remember)
3. On a hybrid computer consisting of a digital computer and an analog computer it is software for a DC and a patch board for the analog part.
4. On a hybrid computer consisting of a digital computer and a QC, I expect, it is software for a DC and a patch board for the QC.

The advantage in a PC is that all the intermediate results in a calculation leading to a software error can be displayed.
These messages will be repeated when the same program is repeated and will change when the program is modified and corrected (as expected).

IN a QC this predictability does not exist, specific when the application is implemented on a hybrid system, as explained above in #4. That means there are 3 causes of problems: In the program part of the DC, in the hardware of the QC and in the application build via the patch board on the QC. This means when the output is not as expected you don't know what the cause is. This could lead to a program modification in the DC while the cause was in the QC hardware or with the usage of patch board.

Feedback

Back to Shor's Algorithm - 10 Questions
Back to my home page Contents of This Document